package search;

import java.util.ArrayList;
import java.util.Arrays;

public class Fibonacci {
    public static int MaxSize = 100;

    public static void main(String[] args) {
        logarithm(1000, 100, 1000);
        runTime(100000, 10000, 1000000);
    }

    /**
     * 斐波那契数列
     *
     * @return
     */
    public static int[] fib() {
        int[] f = new int[MaxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 斐波那契查找
     *
     * @param array
     * @param num
     * @return
     */
    public static int fibonacci(ArrayList<Integer> array, int num) {
        int low = 0;
        int high = array.size() - 1;
        int k = 0;
        int midIndex = 0;
        int f[] = fib();
        while (high > f[k] - 1) {
            k++;
        }
        int[] arr = new int[array.size()];
        for (int j = 0; j < arr.length; j++) {
            arr[j] = array.get(j);
        }
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        while (low <= high) {
            midIndex = low + f[k - 1] - 1;
            if (num < temp[midIndex]) {
                high = midIndex - 1;
                k--;
            } else if (num > temp[midIndex]) {
                low = midIndex + 1;
                k -= 2;
            } else {
                if (midIndex <= high) {
                    return midIndex;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }

    /**
     * 打印数组
     *
     * @param array
     */
    public static void show(ArrayList<Integer> array) {
        for (int i = 0; i < array.size(); i++) {
            System.out.print(array.get(i) + " ");
        }
        System.out.println();
    }

    /**
     * 产生无重复数据的有序随机数组
     *
     * @param length
     * @return
     */
    public static ArrayList<Integer> getRandomArray(int length, int numRange) {
        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            int num = (int) (Math.random() * numRange);
            while (array.contains(num)) {
                num = (int) (Math.random() * numRange);
            }
            array.add(num);
        }
        array.sort(Integer::compareTo);
        return array;
    }

    /**
     * 对数器
     *
     * @param testNum
     * @param arrayLen
     * @param numRange
     */
    public static void logarithm(int testNum, int arrayLen, int numRange) {
        for (int i = 0; i < testNum; i++) {
            ArrayList<Integer> randomArray = getRandomArray(arrayLen, numRange);
            for (int expectedIndex = 0; expectedIndex < randomArray.size() - 1; expectedIndex++) {
                int actualIndex = fibonacci(randomArray, randomArray.get(expectedIndex));
                if (actualIndex != expectedIndex) {
                    show(randomArray);
                    System.out.println("num:" + randomArray.get(expectedIndex) + "\nexpectedIndex:" + expectedIndex + "\nactualIndex:" + actualIndex);
                    return;
                }
            }
        }
        System.out.println("true");
    }

    /**
     * 算法运行时间
     *
     * @param testNum
     * @param arrayLen
     * @param numRange
     */
    public static void runTime(int testNum, int arrayLen, int numRange) {
        ArrayList<Integer> randomArray = getRandomArray(arrayLen, numRange);
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < testNum; i++) {
            int index = (int) (Math.random() * arrayLen);
            fibonacci(randomArray, randomArray.get(index));
        }
        long endTime = System.currentTimeMillis();
        long consumingTime = (endTime - startTime);
        System.out.println("startTime:" + startTime + "\nendTime:" + endTime + "\ntestNum：" + testNum + "\tconsumingTime:" + consumingTime);
    }
}
